#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <list>
using namespace std;

// 最后一块石头的重量
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for (int e : stones) pq.push(e);
        while (pq.size() > 1)
        {
            int x = pq.top(); 
            pq.pop();
            int y = pq.top();
            pq.pop();
            if (x != y) pq.push(x - y);
        }
        return pq.size() == 1 ? pq.top() : 0;
    }
};

// 数据流中的第K大元素
class KthLargest {
    priority_queue<int, vector<int>, greater<int>> pq;// 小根堆
    int _k;
public:
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for (int e : nums)
        {
            pq.push(e);
            if (pq.size() > _k) pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        if (pq.size() > _k) pq.pop();
        return pq.top();
    }
};

// 前K个高频单词
class Solution {
    using psi = pair<string, int>;
    
    struct cmp{
        bool operator()(const psi& p1, const psi& p2)
        {
            if (p1.second == p2.second)
            {
                return p1.first < p2.first;// 大根堆
            }
            return p1.second > p2.second;// 小根堆
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> hash;
        for (auto &e : words) hash[e]++;
        priority_queue<psi, vector<psi>, cmp> pq;
        for (auto &e : hash)
        {
            pq.push(e);
            if (pq.size() > k) pq.pop();
        }
        vector<string> ret(k);
        while (!pq.empty())
        {
            ret[--k] = pq.top().first;
            pq.pop();
        }
        return ret;
    }
};

// 数据流的中位数
class MedianFinder {
    priority_queue<int> left;// 大根堆
    priority_queue<int, vector<int>, greater<int>> right;// 小根堆
public:
    MedianFinder() {}
    
    void addNum(int num) {
        if (left.size() == right.size())
        {
            if (left.size() && num <= left.top()) left.push(num);
            else
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else{
            if (num <= left.top())
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else right.push(num);
        }
    }
    
    double findMedian() {
        if (left.size() == right.size()) return (left.top() + right.top()) / 2.0;
        else return left.top();
    }
};